//class Solution {
//public:
//    priority_queue<int> pq;
//    int k;
//    int kthSmallest(TreeNode* root, int _k) {
//        k = _k;
//        dfs(root);
//        return pq.top();
//    }
//
//    void dfs(TreeNode* root)
//    {
//        if (root == nullptr) return;
//        pq.push(root->val);
//        if (pq.size() > k)
//            pq.pop();
//        dfs(root->left);
//        dfs(root->right);
//    }
//};


//class Solution {
//public:
//    long long prev = LLONG_MIN;
//    bool isValidBST(TreeNode* root) {
//        return dfs(root);
//    }
//
//    bool dfs(TreeNode* root)
//    {
//        if (root == nullptr) return true;
//        if (root->left && !dfs(root->left)) return false;
//        if (root->val <= prev)   return false;
//        prev = root->val;
//        return dfs(root->right);
//    }
//};



//class Solution {
//public:
//    int ret = 0;
//    int kthSmallest(TreeNode* root, int k) {
//        dfs(root, k);
//        return ret;
//    }
//
//    void dfs(TreeNode* root, int& k)
//    {
//        if (root == nullptr) return;
//        dfs(root->left, k);
//        if (--k == 0)
//        {
//            ret = root->val;
//            return;
//        }
//        dfs(root->right, k);
//    }
//};



